package week1;


/**
 * 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：37.7 MB, 在所有 Java 提交中击败了92.17% 的用户
 *
 */
public class Week1TrappingRainWater {

    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int capacity = 0;
        int leftMax = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    capacity += (leftMax - height[left]);
                }
                ++left;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    capacity += (right_max - height[right]);
                }
                --right;
            }
        }
        return capacity;

    }
}
